package com.atwy.graph.undirectedgraph;

/**
 * @Author: 小王子火
 * @Date: 2022/3/15
 * 判断图G是否是无环图？
 */
public class Cycle {
    /**
     * 记录某个顶点是否被访问到
     */
    private boolean[] marked;
    /**
     * 该图是否有环
     */
    private boolean hasCycle;

    public Cycle() {
    }

    public Cycle(IGraph graph) {
        marked = new boolean[graph.V()];
        for (int s=0;s<graph.V();s++){
            if(!marked[s]){
                dfs(graph,s,s);
            }
        }
    }

    /**
     * 深度遍历
     * 可以理解为从v出发，沿一个邻接点w1，路径一直走到头，把所到节点标记为已访问
     * 之后再从v出发，沿另一个邻接点w2，路走，如果这时发现有个节点居然被访问到了，
     * 说明存在路径v-w1-..-w2,和v-w2路径，也就是v到w2有两条不同的路径，则说明存在环
     * @param graph
     * @param v
     * @param u
     */
    private void dfs(IGraph graph,int v,int u){
        marked[v] = true;
        for (int w : graph.adj(v)){
            if(!marked[w]){
                dfs(graph,w,v);
            }else if(w!=u){
                hasCycle = true;
            }
        }
    }

    public boolean hasCycle(){
        return hasCycle;
    }

}
